#include <iostream>
using namespace std;

int naivePatternMatching(string text, string pattern) {
    int m = text.length();
    int n = pattern.length();

    for (int i = 0; i <= m - n; i++) {
        int j;
        for (j = 0; j < n; j++) {
            if (text[i + j] != pattern[j]) {
                break;
            }
        }
        if (j == n) {
            return i; 
        }
    }

    return -1; 
}

void buildLPS(string pattern, int *lps) {
    int n = pattern.length();
    int len = 0;

    lps[0] = 0;
    int i = 1;
    
    while (i < n) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        }
        else {
            if (len != 0) {
                len = lps[len - 1];
            }
            else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int kmpPatternMatching(string text, string pattern) {
    int m = text.length();
    int n = pattern.length();

    int lps[n]; 
    buildLPS(pattern, lps);

    int i = 0; 
    int j = 0; 
    while (i < m) {
        if (pattern[j] == text[i]){
            j++;
            i++;
        }

        if (j == n){
            return i - j; 
            j = lps[j - 1];
        }
        else if (i < m && pattern[j] != text[i]){
            if (j != 0){
                j = lps[j - 1];
            }
            else{
                i++;
            }
        }
    }
    
    return -1; 
}

void buildBadCharTable(string pattern, int badchar[256]) {
    int n = pattern.length();
    
    for (int i = 0; i < 256; i++) {
        badchar[i] = -1;
    }

    for (int i = 0; i < n; i++) {
        badchar[(int)pattern[i]] = i;
    }
}

int boyerMoorePatternMatching(string text, string pattern) {
    int m = text.length();
    int n = pattern.length();

    int badchar[256];
    buildBadCharTable(pattern, badchar);

    int s = 0; 
    while (s <= (m - n)) {
        int j = n - 1;
        while (j >= 0 && pattern[j] == text[s + j]) {
            j--;
        }
        
        if (j < 0) {
            return s;  
            s += (s + n < m) ? n - badchar[(int)text[s + n]] : 1;
        }
        else {
            s += max(1, j - badchar[(int)text[s + j]]);
        }
    }

    return -1; 
}

int main() {
    string text = "ABCDABDABABCEABCDABCA";
    string pattern = "ABCDABCA";

    int result1 = naivePatternMatching(text, pattern);
    cout << "Naive pattern matching result: " << result1 << endl;

    int result2 = kmpPatternMatching(text, pattern);
    cout << "KMP pattern matching result: " << result2 << endl;

    int result3 = boyerMoorePatternMatching(text, pattern);
    cout << "Boyer-Moore pattern matching result: " << result3 << endl;

    return 0;
}